import java.util.*;

public class Test {
    /*
    题目 1：有效三角形的个数
     */
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);

        int n = nums.length;
        int count = 0;

        for(int i = n - 1; i >= 2; i--){
            int left = 0;
            int right = i - 1;
            while(left < right){
                if(nums[left] + nums[right] > nums[i]){
                    count += (right - left);
                    right--;
                }else{
                    left++;
                }
            }
        }
        return count;
    }

    /*
    题目 2：和为 s 的两个数字
     */
    public int[] twoSum(int[] nums, int target) {
        int[] arr = new int[2];

        int n = nums.length;
        int left = 0;
        int right = n - 1;

        while(left < right){
            if(nums[left] + nums[right] > target){
                right--;
            }else if(nums[left] + nums[right] < target){
                left++;
            }else{
                arr[0] = nums[left];
                arr[1] = nums[right];
                return arr;
            }
        }

        return arr;
    }

    /*
    题目 3：三数之和
     */
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);

        List<List<Integer>> lists = new LinkedList<>();

        int n = nums.length;
        int i = 0;

        while(i < n - 2){
            int a = nums[i];
            // 当固定数 a 大于 0 时，排序完之后的后两个数都是大于 0 的
            // 根本就不可能三者和等于0，所以直接 break 出来即可。
            if(a > 0){
                break;
            }
            int target = - a;

            int left = i + 1;
            int right = n - 1;

            while(left < right){
                List<Integer> list = new LinkedList<>();
                if(nums[left] + nums[right] > target){
                    right--;
                }else if(nums[left] + nums[right] < target){
                    left++;
                }else{
                    int b = nums[left];
                    int c = nums[right];
                    list.add(a);
                    list.add(b);
                    list.add(c);
                    lists.add(list);
                    right--;
                    left++;
                    while(left < n && left < right && nums[left] == b){
                        left++;
                    }

                    while(right < n && left < right && nums[right] == c){
                        right--;
                    }
                }
            }

            i++;
            while(i < n - 2 && nums[i] == a){
                i++;
            }

        }

        return lists;
    }

    public List<List<Integer>> threeSum1(int[] nums) {
        List<List<Integer>> lists = new LinkedList<>();

        Arrays.sort(nums);

        int n = nums.length;

        for(int i = 0; i < n - 2; ){
            int left = i + 1;
            int right = n - 1;
            int target = -nums[i];

            while(left < right){
                int sum = nums[left] + nums[right];

                if(sum > target){
                    right--;
                }else if(sum < target){
                    left++;
                }else{
                    List<Integer> list = new LinkedList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    lists.add(list);

                    left++;
                    right--;

                    while(left < right && nums[left] == nums[left - 1]){
                        left++;
                    }
                    while(left < right && nums[right] == nums[right + 1]){
                        right--;
                    }
                }
            }
            i++;
            while(i < n - 2 && nums[i] == nums[i - 1]){
                i++;
            }
        }
        return lists;
    }

    /*
    题目 4：四数之和
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> lists = new LinkedList<>();
        Arrays.sort(nums);

        int n = nums.length;

        for(int i = 0; i < n - 3;){
            for(int j = i + 1; j < n - 2;){
                int left = j + 1;
                int right = n - 1;
                long tg = (long)target - nums[i] - nums[j];

                while(left < right){
                    int sum = nums[left] + nums[right];
                    if(sum > tg){
                        right--;
                    }else if(sum < tg){
                        left++;
                    }else{
                        List<Integer> list = new LinkedList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[left]);
                        list.add(nums[right]);
                        lists.add(list);

                        left++;
                        right--;

                        while(left < right && nums[left] == nums[left - 1]){
                            left++;
                        }
                        while(left < right && nums[right] == nums[right + 1]){
                            right--;
                        }
                    }
                }
                j++;
                while(j < n - 2 && nums[j] == nums[j - 1]){
                    j++;
                }
            }
            i++;
            while(i < n - 3 && nums[i] == nums[i - 1]){
                i++;
            }
        }
        return lists;
    }

    /*
    滑动窗口！
     */
    /*
    题目 5：长度最小的子数组
     */
    // 数组中，全是正整数，利用了 和 的单调性！
    // 会有一个疑问把，left++ 之后，sum >= target，right 是否可以 right-- ?
    // 答案是不行的，因为对于原本的 left，是加上了 right 对应的值，sum >= target 才成立
    // 如果 left++，right--, sum 肯定是小于 target 的！right 要么不变，要么 right++!
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int sum = 0;
        int len = n + 1;

        for(int left = 0, right = 0; right < n; right++){
            // 1. 进窗口
            sum += nums[right];
            // 2. 判断
            while(sum >= target){
                len = Math.min(len, right - left + 1);
                sum -= nums[left];
                left++;// 3. 出窗口
            }

        }

        return len == n + 1 ? 0 : len;
    }

    /*
    题目 6：无重复字符的最长子串
     */
    public static int lengthOfLongestSubstring1(String ss) {
        char[] s = ss.toCharArray();
        int n = s.length;
        Set<Character> set = new HashSet<>();
        int len = 0;

        for(int left = 0, right = 0; right < n; right++){
            while(right < n && !set.contains(s[right])){
                set.add(s[right]);
                right++;
            }

            len = Math.max(len, right - left);

            while(right < n && s[left] != s[right]){
                set.remove(s[left]);
                left++;
            }
            left++;
        }

        return len;
    }

    public static void main1(String[] args) {
        String s = "a";
        int ret = lengthOfLongestSubstring(s);
        System.out.println(ret);
    }

    // 时间复杂度 O(n)
    public static int lengthOfLongestSubstring(String ss) {
        // 使用 数组 来模拟哈希表
        int[] hash = new int[128];

        char[] s = ss.toCharArray(); // 这一步空间复杂度 O(n)

        int n = s.length;
        int len = 0;

        for(int left = 0, right = 0; right < n; right++){
            hash[s[right]]++; // 进入窗口
            // 这一步的处理非常巧妙！
            while(hash[s[right]] > 1){ // 为 2 的时候，重复了
                hash[s[left]]--;
                left++;
            }
            len = Math.max(len, right - left + 1);

        }
        return len;
    }

    /*
    题目 7：最大连续 1 的个数Ⅲ
     */
    public int longestOnes(int[] nums, int k) {
        int n = nums.length;
        int len = 0;
        for(int left = 0, right = 0, zero = 0 ; right < n; right++){
            if(nums[right] == 0) zero++;
            while(zero > k){
                if(nums[left++] == 0) zero--;
            }
            len = Math.max(len, right - left + 1);
        }

        return len;
    }


}
